Chiffrement affine - Corrigé

Énoncé

On assimile les \(26\) lettres de l'alphabet : A, B, ..., Z aux nombres \(0\) , \(1\) , ..., \(25\) . Le chiffrement affine consiste à coder chaque lettre de l'alphabet en appliquant à son rang \(x\) (compris entre \(0\) et \(25\) ) une fonction affine \(f(x)=ax+b\) , puis le rang \(y\) de la lettre codée est le reste dans la division euclidienne de \(f(x)\) par \(26\) .

Autrement dit, on a \(y=f(x)\) et \(y \in \left\lbrace 0 ; ... ;25 \right\rbrace\) , où \(f\) est la fonction de codage définie par  \(f(x) \equiv ax+b \ [26]\)  avec \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}\) choisis de manière pertinente.

Dans la suite de cet exercice, on suppose que la fonction de codage est \(f(x) \equiv 17x+15 \ [26]\) .

Pour répondre aux questions suivantes, on pourra utiliser un tableur.

1. Coder le mot "MATHEMATIQUES".

2. a. Déterminer un couple d'entiers \((u;v) \in \mathbb{Z}^2\) tels que \(17u+26v=1\) .
    b. En déduire un inverse de \(17\) modulo \(26\) .
    c. Montrer que la fonction de décodage, c'est-à-dire la fonction \(g\) telle que \(x=g(y)\) , peut s'écrire : \(g(y) \equiv 23y+19 \ [26]\) .
    d. Décoder alors le mot "HLTUKZOZ".

Solution

1. "LPAEFLPAVBRFJ"

2. a. On applique l'algorithme d'Euclide pour  \(26\)  et  \(17\)  :

\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline a&b&q&r\\ \hline 26&17&1&9\\ \hline 17&9&1&8\\ \hline 9&8&1&1 \\ \hline 8&1&8&0 \\ \hline \end{array} \begin{array}{ll}\ & \\ \times 2 & \text{suppression du reste } 9 \\ \times (-1)& \text{suppression du reste } 8\\ \times 1& \text{conservation du PGCD}\\ & \end{array}\end{align*}\)   

En additionnant les lignes après avoir éliminé les restes intermédiaires, on obtient :  \(\begin{align*}26 \times 2+17 \times (-1)=17 \times 1 \times 2+1& \ \ \Longleftrightarrow \ \ 17 \times (-3)+26 \times 2=1\end{align*}\)  donc le couple  \((u;v)=(-3;2)\) convient.

    b. D'après la question 2.a, on a  \(17 \times (-3)+26 \times 2=1\) donc en écrivant cette égalité modulo \(26\) , on obtient \(17 \times (-3) \equiv 1 \ [26]\) . Ainsi, \(-3\) est un inverse de \(17\) modulo \(26\) .

    c. On a \(y \equiv f(x) \equiv 17x+15 \ [26]\) , donc en multipliant par \((-3)\) , on obtient
\(\begin{align*}-3y \equiv -3 \times 17x-45 \ [26]& \ \ \Longleftrightarrow \ \ -3y \equiv x-45 \ [26]\\ & \ \ \Longleftrightarrow \ \ x \equiv -3y+45 \ [26]\\ & \ \ \Longleftrightarrow \ \ x \equiv 23y+19 \ [26]\end{align*}\)  

car \(-3 \times 17 \equiv 1 \ [26]\) , \(-3 \equiv 23 \ [26]\) et \(45 \equiv 19 \ [26]\) .

Notons que les équivalences ci-dessus viennent du fait que  \(17\)  est un inverse de  \(-3\)  modulo  \(26\)  : pour « revenir en arrière » après avoir multiplié par  \(-3\) , il faut multiplier par  \(17\) .

La fonction de décodage peut donc bien s'écrire \(g(y) \equiv 23y+19 \ [26]\) .

    d. "COMPLEXE"